package algorithm.niuke;

public class K回文子串 {
    /*
     * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
     * 
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
     * 
     * 示例 1:
     * 
     * 输入: "abc" 输出: 3 解释: 三个回文子串: "a", "b", "c". 示例 2:
     * 
     * 输入: "aaa" 输出: 6 说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa". 注意:
     * 
     * 输入的字符串长度不会超过1000。
     */
    boolean log = false;

    public int countSubstrings(String s) {
        char[] chs = s.toCharArray();
        int len = chs.length;
        int[][] dp = new int[len + 2][len + 2];
        int sum = 0;
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
            sum++;
            for (int k = 0; k < i; k++) {
                if (chs[k] == chs[i]) {
                    if (k == i - 1) {
                        dp[k][i] = 1;
                        sum++;
                    } else {
                        dp[k][i] += dp[k + 1][i - 1];
                        sum += dp[k + 1][i - 1];
                    }
                }
            }
        }
        return sum;
    }

    public int fun2(String s) {
        int len = s.length();
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += count(s, i, i, len);
            sum += count(s, i, i + 1, len);
        }
        return sum;
    }

    int count(String s, int start, int end, int len) {
        int num = 0;
        while (start >= 0 && end < len && s.charAt(start) == s.charAt(end)) {
            num++;
            start--;
            end++;
        }
        return num;
    }

    public static void main(String[] args) {
        K回文子串 run = new K回文子串();
        System.out.println(run.countSubstrings("aaa"));
    }
}
